
// Definition for a binary tree node.
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}
function createTree(arr) {
  let nodeArr = [];
  for(let i = 0; i < arr.length; i++) {
    let node = new TreeNode(arr[i]);
    nodeArr.push(node);
  }
  for(let i = 0; i < nodeArr.length; i++) {
    if(2 * i + 1 < nodeArr.length) {
      nodeArr[i].left = nodeArr[2 * i + 1];
    }
    if(2 * i + 2 < nodeArr.length) {
      nodeArr[i].right = nodeArr[2 * i + 2];
    }
  }
  return nodeArr[0];
}
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
  let nodeArr = [];
  function preView(node, depth) {
    if(!node) return ;
    nodeArr.push({
      val: node.val,
      depth
    });
    preView(node.left, depth + 1);
    preView(node.right, depth + 1);
  }
  preView(root, 0);
  nodeArr.sort((a, b) => a.depth - b.depth);
  let result = [], num = 0;
  for(let i = 0; i < nodeArr.length; i++) {
    if(result[nodeArr[i].depth] != undefined) {
      result[nodeArr[i].depth] += nodeArr[i].val;
      num++;
    } else {
      if(i != 0 && num) {
        result[nodeArr[i].depth - 1] /= num;
      }
      result[nodeArr[i].depth] = nodeArr[i].val;
      num = 1
    }
  }
  result[result.length - 1] /= num;
  return result;
};
let root = [3,9,20,null,null,15,7];
// console.log(averageOfLevels(createTree(root)));
// root = [3,9,20,15,7];
// console.log(averageOfLevels(createTree(root)));
root = [3,1,5,0,2,4,6];
console.log(averageOfLevels(createTree(root)));
